package com.ken.algorithms.stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * <ul>
 * <li>Title: MainCD101</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/20 0020 上午 9:49
 */
public class MainCD101 {

    /**
     *【题目链接】：https://www.nowcoder.com/practice/e3d18ffab9c543da8704ede8da578b55?tab=answerKey
     * NowCoder：CD101. 单调栈结构
     * 【题目描述】：
     *
     * 给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
     *
     * 【解题思路】：
     *
     * 做了这么多单调栈的题目，各位大概也找到规律了吧，
     * 如果题目找的是某个比较小的值，就使用单调递增栈，如果找的是某个比较大的值，就是用单调递减栈。
    */
    public static void main(String[] args) {
        int [] arr ={3,4,1,5,6,2,7};
        int[][] leftRightMin = findLeftRightMin(arr);

        for (int i = 0; i < leftRightMin.length; i++) {
            System.out.println(Arrays.toString(leftRightMin[i]));
        }
    }


    private static int[][] findLeftRightMin(int[] arr) {
        int[][] res = new int[arr.length][2];
        for (int i = 0; i < res.length; i++) {
            res[i][0] =-1;
            res[i][1] =-1;
        }
        Stack<Integer> stack = new Stack<Integer>();

        int cur = 0;
        boolean fz = false;

        for (int i = 0; i <arr.length ; i++) {
            // 记住 这样 处理 是 针对单调递增的栈
            // 后面的数 小于 前面的数
            // 这样处理栈 遇到后面的值小于栈顶的值 栈顶被移除  此时 栈顶的值可能是后面某个值左侧 最近的比自身小的值 这样 他们两就不能对比(左侧不能对比)
            // 如果不加上arr[stack.peek()] >= arr[i]  保证不了 单调递增性 因为违反了这个条件  栈顶的数据就会出栈  剩下的数据肯定是单调递增的
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]){
                cur = stack.pop();
                int leftRight = stack.isEmpty()?-1:stack.peek();
                int rigthInd = i;
                res[cur][0] = leftRight;
                res[cur][1] = rigthInd;
            }

            stack.push(i);
        }

        // 如果不处理这些 剩下的单调递增的数据  就没有处理
        while (!stack.isEmpty()){
            cur = stack.pop();
            int leftRight = stack.isEmpty()?-1:stack.peek();
            res[cur][0] = leftRight;
        }

        return res;

    }
}
